SP7258 SUBLEX - Lexicographical Substring Search

一道后缀自动机的简单题。

首先我们要求出经过后缀自动机上的每一个点的不同子串数量，这个可以用拓扑序$dp$解决。

设 $s$ 为当前找到的子串，为了使它字典序更大，我们考虑在它后面添加字符。

首先，这个字符必须出现在该节点的转移上，由于 $s+'a~'$ 的字典序一定比 $s+'b~'$ 的字典序小，所以我们就可以用类似二叉搜索树的方法来解决这个二十六叉搜索树。

注意唯一不同的是求出答案后$break$。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 90000 , MAXK = 26;
struct Suffix_Automaton {
	int Root , Size , Last , Maxlen[ 2 * MAXN + 5 ]; 
	int Trans[ 2 * MAXN + 5 ][ MAXK + 5 ] , Link[ 2 * MAXN + 5 ];
	long long dp[ 2 * MAXN + 5 ];
	
	Suffix_Automaton( ) { Root = Size = Last = 1; }
	
	void Copy( int u , int v ) {
		for( int i = 1 ; i <= MAXK ; i ++ )
			Trans[ u ][ i ] = Trans[ v ][ i ];
	}
	void Extend( int chr ) {
		int Newnode = ++ Size , u = Last;
		Maxlen[ Newnode ] = Maxlen[ u ] + 1;
		
		for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
			Trans[ u ][ chr ] = Newnode;
		
		if( !u ) Link[ Newnode ] = 1;
		else {
			int v = Trans[ u ][ chr ];
			
			if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
			else {
				int w = ++ Size;
				Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
				for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
				Link[ w ] = Link[ v ];
				Link[ v ] = Link[ Newnode ] = w;	
			}
		}
		Last = Newnode;
	}
	void Build( char *str ) {
		int len = strlen( str );
		for( int i = 0 ; i < len ; i ++ )
			Extend( str[ i ] - 'a' + 1 );
		Sort( );
	}
	
	int tot[ 2 * MAXN + 5 ] , Topu[ 2 * MAXN + 5 ];
	void Sort( ) {
		for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
		for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
		for( int i = 1 ; i <= Size ; i ++ ) Topu[ tot[ Maxlen[ i ] ] -- ] = i; 
	} 
	
	void Dp( ) {
		for( int i = Size ; i >= 1 ; i -- ) {
			int u = Topu[ i ];
			dp[ u ] = ( u > 1 );
			for( int k = 1 ; k <= MAXK ; k ++ )
				if( Trans[ u ][ k ] ) dp[ u ] += dp[ Trans[ u ][ k ] ]; 
		}
	}
	void dfs( int u , int k ) {
		if( !k ) return;
		for( int i = 1 ; i <= MAXK ; i ++ ) {
			int v = Trans[ u ][ i ];
			if( !v ) continue;
			if( k > dp[ v ] )
				k -= dp[ v ];
			else {
				putchar( i + 'a' - 1 );
				dfs( v , k - 1 ); //当前可以不加v,字典序会比后面的小
				break;
			}
		}
	}
}SAM;

int t , k;
char str[ MAXN + 5 ];

int main( ) {
	scanf("%s %d", str , &t );
	SAM.Build( str ); SAM.Dp();
	
	while( t -- ) {
		scanf("%d",&k);
		SAM.dfs( SAM.Root , k );
		putchar('\n');
	}
	return 0;
}